package org.example.SolutionNew003;

public class DoubleTree005 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
//        root.right = new TreeNode(2);
//        root.left.right = new TreeNode(3);
        DoubleTree005 dt = new DoubleTree005();
        System.out.println(dt.diameterOfBinaryTree(root));
    }

    int maxNum=Integer.MIN_VALUE;

    public int diameterOfBinaryTree1(TreeNode root) {
        //dp遍历过程中不仅要记录当前节点的最大值，还要比较总的最大值;
        int res=rootMaxLen(root);
        return Math.max(maxNum, res);
    }

    public int rootMaxLen(TreeNode root) {
        if(root.left==null&&root.right==null) return 0;
        if(root.left==null||root.right==null) return root.left==null?rootMaxLen(root.right)+1:rootMaxLen(root.left)+1;
        int left=rootMaxLen(root.left);
        int right=rootMaxLen(root.right);
        maxNum=Math.max(maxNum,left+right+2);
        return Math.max(left,right)+1;
    }

    public int diameterOfBinaryTree(TreeNode root) {
        //注意到 路径为节点数-1
        maxNum=1;   //题目规定至少有一个节点
        depth(root);
        return maxNum-1;
    }

    public int depth(TreeNode root) {
        if(root==null) return 0;

        int left=depth(root.left);
        int right=depth(root.right);

        maxNum=Math.max(maxNum,left+right+1);

        return Math.max(left,right)+1;
    }
}
